<!DOCTYPE html>
<html lang="zh-hans">
<head>
  <meta charset="utf-8">
  <meta name="generator" content="pandoc">
  <meta name="author" content="codgician">
  <title>浅谈置换群</title>
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">
  <link rel="stylesheet" href="assets/revealjs/css/reset.css">
  <link rel="stylesheet" href="assets/revealjs/css/reveal.css">
  <style>
    code{white-space: pre-wrap;}
    span.smallcaps{font-variant: small-caps;}
    span.underline{text-decoration: underline;}
    div.column{display: inline-block; vertical-align: top; width: 50%;}
    div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
    ul.task-list{list-style: none;}
  </style>
  <link rel="stylesheet" href="assets/revealjs/css/theme/black.css" id="theme">
  <!-- Printing and PDF exports -->
  <script>
    var link = document.createElement( 'link' );
    link.rel = 'stylesheet';
    link.type = 'text/css';
    link.href = window.location.search.match( /print-pdf/gi ) ? 'assets/revealjs/css/print/pdf.css' : 'assets/revealjs/css/print/paper.css';
    document.getElementsByTagName( 'head' )[0].appendChild( link );
  </script>
  <!--[if lt IE 9]>
  <script src="assets/revealjs/lib/js/html5shiv.js"></script>
  <![endif]-->
  <script src="assets/katex/katex.min.js"></script>
  <script>document.addEventListener("DOMContentLoaded", function () {
   var mathElements = document.getElementsByClassName("math");
   for (var i = 0; i < mathElements.length; i++) {
    var texText = mathElements[i].firstChild;
    if (mathElements[i].tagName == "SPAN") {
     katex.render(texText.data, mathElements[i], {
      displayMode: mathElements[i].classList.contains('display'),
      throwOnError: false,
      fleqn: false
     });
  }}});
  </script>
  <link rel="stylesheet" href="assets/katex/katex.min.css" />
</head>
<body>
  <div class="reveal">
    <div class="slides">

<section id="title-slide">
  <h1 class="title">浅谈置换群</h1>
  <p class="author">codgician</p>
  <p class="date">2020.03.14</p>
</section>

<section>
<section id="relation" class="title-slide slide level1">
<h1>关系</h1>
<ul>
<li>集合的<strong>笛卡尔积 (Cartesian product)</strong>： <span class="math display">
A \times B = \left\{ (a, b) \mid a \in A, b \in B \right\}
</span></li>
<li>设 <span class="math inline">A</span> 是集合，集合 <span class="math inline">A \times A</span> 的每个子集 <span class="math inline">R</span> 叫做集合 <span class="math inline">A</span> 上的一个<strong>关系 (relation)</strong>。</li>
<li>若 <span class="math inline">(a, b) \in R</span>，则称 <span class="math inline">a</span> 和 <span class="math inline">b</span> 有关系 <span class="math inline">R</span>，记作 <span class="math inline">aRb</span>。</li>
</ul>
</section>
<section id="equivalence-relation" class="slide level2">
<h2>等价关系</h2>
<p>若集合 <span class="math inline">A</span> 上的关系 <span class="math inline">\sim</span> 满足如下条件：</p>
<ul>
<li><strong>自反性</strong>：<span class="math inline">\forall a \in A</span>，<span class="math inline">a \sim a</span>；</li>
<li><strong>对称性</strong>：<span class="math inline">\forall a, b \in A</span>，若 <span class="math inline">a \sim b</span> 则 <span class="math inline">b \sim a</span>；</li>
<li><strong>传递性</strong>：<span class="math inline">\forall a, b \in A</span>，若 <span class="math inline">a \sim b, \ b \sim c</span>，则 <span class="math inline">a \sim c</span>；</li>
</ul>
<p>则称 <span class="math inline">\sim</span> 是<strong>等价关系 (equivalence relation)</strong></p>
</section>
<section class="slide level2">

<p><span class="math display">
a \sim b := a \equiv b \pmod 7
</span></p>
<ul>
<li>自反性？对称性？传递性？</li>
<li>看起来可以把所有自然数分成 <span class="math inline">7</span> 类……</li>
</ul>
</section>
<section id="equivalence-class" class="slide level2">
<h2>等价类</h2>
<p>设 <span class="math inline">\sim</span> 是 <span class="math inline">A</span> 上的等价关系，<span class="math inline">\forall a \in A</span>，<span class="math inline">[a]</span> 表示 <span class="math inline">A</span> 中与 <span class="math inline">a</span> 等价的全部元素构成的集合：</p>
<p><span class="math display">
[a] = \{ b \sim a \mid b \in A \}
</span></p>
<p>称 <span class="math inline">[a]</span> 为 <span class="math inline">a</span> 所在的<strong>等价类 (equivalence class)</strong>。</p>
</section>
<section class="slide level2">

<p><strong>若 <span class="math inline">a, b \in A</span> 且 <span class="math inline">[a] \cap [b] \neq \emptyset</span>，则 <span class="math inline">[a] = [b]</span>。</strong></p>
<div class="fragment fade-in-then-out" style="height:0">
<ul>
<li>假设 <span class="math inline">k_1 \in [a]</span> 且 <span class="math inline">k_1 \notin [b]</span>，<span class="math inline">k_2 \in [a] \cap [b]</span>；</li>
<li>则有 <span class="math inline">k_1 \sim a, \ k_2 \sim a, \ k_2 \sim b</span>；</li>
<li>由传递性得 <span class="math inline">k_1 \sim b</span>，与假设不符。</li>
</ul>
</div>
<div class="fragment">
<ul>
<li>集合 <span class="math inline">A</span> 可看作一些两两不相交的等价类的并： <span class="math display">
A = \bigcup\limits_{a \in R} [a] \text{（两两不相交之并）}
</span></li>
<li><span class="math inline">A</span> 上的每个等价关系给出集合 <span class="math inline">A</span> 的一个<strong>划分 (partition)</strong>。</li>
</ul>
</div>
<aside class="notes">
<p>关于 <span class="math inline">R</span>，事实上是完全代表系，由等价类 <span class="math inline">[a_i]</span> 中选出一个元素构成，使得 <span class="math inline">A</span> 中每个元素都与 <span class="math inline">R</span> 中的某个元素等价，同时 <span class="math inline">R</span> 中的元素彼此不等价。</p>
<p>对于划分的定义：若 <span class="math inline">A</span> 是它的某些子集 <span class="math inline">\{ A_i | i \in I \}</span> 之并，且 <span class="math inline">A_i</span> 两两不交，则称其为集合 <span class="math inline">A</span> 的一个划分（或分拆）。</p>
<p>我们可以看到，引入等价类的意义就是为了对集合中的元素进行某种程度上的分类。后面要介绍的轨道、陪集等本质上都是基于等价关系的。</p>
</aside>
</section></section>
<section>
<section id="group" class="title-slide slide level1">
<h1>群 <span class="math inline">(G, \cdot)</span></h1>
<p><span class="math inline">G</span> 是非空集合，且二元运算满足：</p>
<ul>
<li>结合律：<span class="math inline">(a \cdot b) \cdot c = a \cdot (b \cdot c)</span></li>
<li>单位元 <span class="math inline">e</span>：<span class="math inline">\forall a \in G, \ ea = ae = a</span></li>
<li>逆元：<span class="math inline">\forall a \in G, \ \exist b \in G \text{ \ s.t. \ } ab = ba = e</span></li>
</ul>
<div class="fragment">
<p>若满足交换律，则称为<strong>交换群</strong></p>
</div>
<aside class="notes">
<p>需要注意的是，构成群不一定要满足交换律。接下来我们会说明为什么对于群左右逆元是相等的。</p>
</aside>
</section>
<section class="slide level2">

<ul>
<li>左右逆元相等：
<ul>
<li><p>设 <span class="math inline">x</span> 是 <span class="math inline">a</span> 的左逆元，<span class="math inline">y</span> 是 <span class="math inline">a</span> 的右逆元，有：</p>
<p><span class="math display">
x = xe = x(ay) = (xa)y = y
</span></p></li>
</ul></li>
<li>满足消去律：
<ul>
<li><span class="math inline">\forall a, b, c \in G, \ ab = ac \Leftrightarrow b = c</span></li>
</ul></li>
</ul>
<aside class="notes">
<p>只要逆元存在就满足消去律：两边都乘上 <span class="math inline">a^{-1}</span> 即可。</p>
</aside>
</section>
<section id="subgroup" class="slide level2">
<h2>子群</h2>
<p>设 <span class="math inline">(G, \cdot)</span> 为群，<span class="math inline">H</span> 是 <span class="math inline">G</span> 的子集，若 <span class="math inline">(H, \cdot)</span> 成群，则称 <span class="math inline">H</span> 为 <span class="math inline">G</span> 的<strong>子群 (subgroup)</strong>，记作 <span class="math inline">H \le G</span>；</p>
</section>
<section id="coset" class="slide level2">
<h2>陪集</h2>
<p>设 <span class="math inline">H \leq G</span>，对于 <span class="math inline">x \in G</span>：</p>
<ul>
<li><span class="math inline">H</span> 的一个<strong>左陪集 (left coset)</strong> <span class="math inline">xH</span>： <span class="math display">
xH = \{ x \cdot h \mid h \in H \}
</span></li>
<li><span class="math inline">H</span> 的一个<strong>右陪集 (right coset)</strong> <span class="math inline">Hx</span>： <span class="math display">
Hx = \{ h \cdot x \mid h \in H \}
</span></li>
</ul>
<aside class="notes">
<p>由于左右陪集相关内容是相似的，所以接下来只会分析左陪集。</p>
</aside>
</section>
<section class="slide level2">

<p><span class="math display">
\begin{aligned}
xH &amp; = \{ x \cdot h \mid h \in H \}
\end{aligned}
</span></p>
<div class="fragment">
<p><span class="math display">
x \sim y := x \in yH
</span></p>
<ul>
<li><strong>自反性</strong>：<span class="math inline">x \in xH</span>；</li>
<li><strong>对称性</strong>：若 <span class="math inline">y \in xH</span>，则 <span class="math inline">x \in yH</span>；</li>
<li><strong>传递性</strong>：若 <span class="math inline">z \in yH, \ y \in xH</span>，则 <span class="math inline">z \in xH</span>。</li>
</ul>
</div>
<aside class="notes">
<p><span class="math inline">x \sim y := x \in yH</span> 是一个等价关系，这意味着我们可以借助陪集对群 <span class="math inline">G</span> 进行划分。</p>
<p>注意陪集不一定是 <span class="math inline">G</span> 的一个子群。</p>
<p>💡 提示:</p>
<ol type="1">
<li>既然 <span class="math inline">H</span> 还是群，那么肯定有单位元；</li>
<li>既然 <span class="math inline">H</span> 中逆元存在，有 <span class="math inline">y = x \cdot h</span>， 自然有 <span class="math inline">x = y \cdot h^{-1}</span> 且 <span class="math inline">h^{-1} \in H</span>；</li>
<li><span class="math inline">z = y \cdot h_1, \ y = x \cdot h_2 \Rightarrow z = x \cdot h_2h_1</span>，又 <span class="math inline">h_2h_1 \in H</span>，自然得证。</li>
</ol>
</aside>
</section>
<section class="slide level2">

<ul>
<li><p>若 <span class="math inline">xH \cap yH \neq \emptyset</span>，则 <span class="math inline">xH = yH</span>；</p></li>
<li><p>利用陪集可以对群 <span class="math inline">G</span> 进行划分（陪集分解）：</p>
<p><span class="math display">
G = \bigcup\limits_{g \in R} gH \text{（两两不相交之并）}
</span></p></li>
</ul>
<aside class="notes">
<p>既然是等价关系，那么可以得到这里的推论。</p>
<p>这里展现了对于群 <span class="math inline">G</span> 的左陪集分解，类似地 <span class="math inline">R</span> 称作 <span class="math inline">G</span> 对 <span class="math inline">H</span> 左陪集的代表元系。<span class="math inline">R</span> 由 <span class="math inline">G</span> 中的元素构成，并且这些用元素生成的左陪集彼此互不相同，与此同时这些左陪集的并集恰好为 <span class="math inline">G</span>。</p>
</aside>
</section>
<section class="slide level2">

<ul>
<li>对于 <span class="math inline">a, b \in H, g \in G</span>，由消去律 <span class="math inline">a \neq b \Leftrightarrow ga \neq gb</span>；</li>
<li>因此，<span class="math inline">\forall g \in R, \ |gH| = |H|</span>: <span class="math display">
|G| = \sum\limits_{g \in R} |gH| 
= \sum\limits_{g \in R} |H| 
= |R| \cdot |H|
</span></li>
</ul>
<aside class="notes">
<p>利用群 <span class="math inline">G</span> 的一个子群 <span class="math inline">H</span>，我们可以借助陪集对 <span class="math inline">G</span> 进行划分。换句话说，群 <span class="math inline">G</span> 一定可以表示成若干个 <span class="math inline">H</span> 的互不相交的左（右）陪集之并，同时这些陪集的大小都是相同的。</p>
<p>把 <span class="math inline">|R|</span> 记作群 <span class="math inline">H</span> 对群 <span class="math inline">G</span> 的指数 <span class="math inline">[G : H]</span>，就可以得到拉格朗日定理……</p>
</aside>
</section>
<section id="lagrange-theorem" class="slide level2">
<h2>拉格朗日定理</h2>
<p>设 <span class="math inline">G</span> 为有限群，<span class="math inline">H \leq G</span>，则：</p>
<p><span class="math display">
|G| = [G : H] \cdot |H|
</span></p>
<p>其中 <span class="math inline">[G : H]</span> 称为群 <span class="math inline">H</span> 对于群 <span class="math inline">G</span> 的<strong>指数 (index)</strong>。</p>
<aside class="notes">
<p>说明 <span class="math inline">G</span> 的子群 <span class="math inline">H</span> 的大小一定是 G 大小的因子。</p>
</aside>
</section></section>
<section>
<section id="permutation" class="title-slide slide level1">
<h1>置换</h1>
<p>一个集合的<strong>置换 (permutation)</strong> 即从该集合映射至自身的双射。</p>
<p><span class="math display">
\sigma = 
\left(\begin{array}{c}
1 &amp; 2 &amp; \dots &amp; n \\
\sigma(1) &amp; \sigma(2) &amp; \dots &amp; \sigma(n)
\end{array}\right)
</span></p>
<p>复合运算: <span class="math inline">(f \circ g)(x) = f(g(x))</span></p>
<aside class="notes">
<p>可以理解成对于 <span class="math inline">1 \sim n</span> 的重排列。</p>
<p>回忆：双射描述的是两个集合间的关系。当然在这里，可以把置换成一种特殊的函数，则双射描述的就是定义域与值域之间的关系。</p>
<ul>
<li>单射：对于定义域里的每一个 <span class="math inline">x</span>，值域里都存在一个 <span class="math inline">y</span> 使得 <span class="math inline">\sigma(x) = y</span>；</li>
<li>满射：对于值域里的每一个 <span class="math inline">y</span>，定义域里都存在一个 <span class="math inline">x</span> 使得 <span class="math inline">y = \sigma(x)</span>；</li>
<li>双射：同时满足单射和满射，即定义域和值域间存在严格的一一对应关系。</li>
</ul>
</aside>
</section>
<section class="slide level2">

<p><span class="math display">
\left(\begin{array}{c} 
1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 
4 &amp; 5 &amp; 1 &amp; 3 &amp; 6 &amp; 2 
\end{array}\right)
</span></p>
<div class="fragment">
<p><span class="math display">
\begin{aligned}
1 &amp; \rightarrow 4 \rightarrow 3 \\
2 &amp; \rightarrow 5 \rightarrow 6
\end{aligned}
</span></p>
<p>任一置换都能被划分成若干不交的映射链？</p>
</div>
<aside class="notes">
<p>如果可以的话，这就意味着我们发现了一种能够更简单表示置换的方式（也就是后面要介绍的轮换表示法）。</p>
</aside>
</section>
<section id="cycle-notation" class="slide level2">
<h2>轮换表示法</h2>
<p><span class="math display"> 
\left(\begin{array}{c}
a_1 &amp; a_2 &amp; \dots &amp; a_n \\
a_2 &amp; a_3 &amp; \dots &amp; a_1
\end{array}\right) \xRightarrow{\text{记作}} (a_1 \enspace a_2 \enspace \dots \enspace a_n)
</span></p>
</section>
<section class="slide level2">

<p><span class="math display">
\left(\begin{array}{c} 
1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\ 
4 &amp; 5 &amp; 1 &amp; 3 &amp; 6 &amp; 2 
\end{array}\right)
= (1 \enspace 4 \enspace 3) \cdot (2 \enspace 5 \enspace 6)
</span></p>
<div class="fragment">
<p><strong>若不计轮换内外的次序，对于任意置换的不交轮换分解是唯一的吗？</strong></p>
</div>
<aside class="notes">
<p>显然不交的轮换在复合时是满足交换律的，但是如果两个轮换相交就不好说了，例如试试计算 (1 2 3) * (3 4) 是否等于 (3 4) * (1 2 3)。</p>
</aside>
</section>
<section class="slide level2">

<ul>
<li>对于恒等置换，显然分解是唯一的；</li>
<li>对于非恒等置换，<span class="math inline">\exist i \text{ \ s.t. \ } \sigma(i) \neq i</span>。
<ul>
<li><span class="math inline">i \rightarrow \sigma(i) \rightarrow \sigma^2(i) \rightarrow \dots</span></li>
<li>由抽屉原理，<span class="math inline">\exist t_1 &lt; t_2 \text{ \ s.t. \ } \sigma^{t_1}(i) = \sigma^{t_2}(i)</span></li>
<li>令 <span class="math inline">t</span> 为使得 <span class="math inline">\sigma^t(i) = i</span> 的最小正整数，则： <span class="math display">
(i \enspace \sigma(i) \enspace \dots \enspace \sigma^{t - 1}(i))
</span> 是一个轮换。</li>
</ul></li>
</ul>
</section>
<section class="slide level2">

<ul>
<li>对于每个这样的 <span class="math inline">i</span> 都如此操作即可构造出一个唯一的不相交轮换分解式：
<ul>
<li>每个元素在分解式中恰好出现 <span class="math inline">1</span> 次；</li>
<li>每个元素所属于的轮换是固定的。</li>
</ul></li>
</ul>
</section>
<section id="power-of-cycle" class="slide level2">
<h2>轮换的幂运算</h2>
<div class="fragment current-visible" style="height:0">
<p><span class="math display">
(1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)
</span></p>
</div>
<aside class="notes">
<p>既然任意置换都可以被分解成若干不交轮换之积，那么如果轮换的幂运算能够快速进行，我们就可以快速地对任意置换进行幂运算。</p>
</aside>
<div class="fragment fade-in-then-out" style="height:0">
<p><span class="math display">
\begin{aligned}
&amp; (1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)^2 \\
&amp; = (1 \enspace 3 \enspace 5) \cdot (2 \enspace 4 \enspace 6)
\end{aligned}
</span></p>
</div>
<div class="fragment fade-in-then-out" style="height:0">
<p><span class="math display">
\begin{aligned}
&amp; (1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)^3 \\
&amp; =  (1 \enspace 4) \cdot (2 \enspace 5) \cdot (3 \enspace 6)
\end{aligned}
</span></p>
</div>
<div class="fragment fade-in-then-out" style="height:0">
<p><span class="math display">
\begin{aligned}
&amp; (1 \enspace 2 \enspace 3 \enspace 4 \enspace 5 \enspace 6)^4 \\
&amp; = (1 \enspace 5 \enspace 3) \cdot (2 \enspace 6 \enspace 4)
\end{aligned}
</span></p>
</div>
</section>
<section class="slide level2">

<p><span class="math display">
\sigma = (a_0 \enspace a_1 \enspace \dots \enspace a_{n - 1})
</span></p>
<ul>
<li><span class="math inline">\sigma^t(a_i) = a_{[(i + t) \bmod n]}</span></li>
<li>令 <span class="math inline">k \in N^{*} \text{ \ s.t. \ } \sigma^{tk}(a_i) = a_i</span>：</li>
</ul>
<div class="fragment current-visible" style="height:0">
<p><span class="math display">
i + tk \equiv i \pmod n
</span></p>
</div>
<div class="fragment">
<p><span class="math display">
tk \equiv 0 \pmod n
</span></p>
<p>最小正整数解：<span class="math inline">k = \frac{n}{\gcd(n, t)}</span></p>
</div>
</section>
<section class="slide level2">

<p><span class="math display">
\sigma = (a_0 \enspace a_1 \enspace \dots \enspace a_{n - 1})
</span></p>
<ul>
<li><p><span class="math inline">\sigma^t</span> 可表示为 <span class="math inline">\gcd(n, t)</span> 个长为 <span class="math inline">\frac{n}{\gcd(n, t)}</span> 的轮换；</p></li>
<li><p><span class="math inline">a_i</span> 所在轮换里第 <span class="math inline">j</span> 个元素为 <span class="math inline">a_{(i + jt) \bmod n}</span>。</p>
<div class="fragment">
<ul>
<li><span class="math inline">a_i</span> 所在轮换内元素下标模 <span class="math inline">\gcd(n, t)</span> 均为 <span class="math inline">i</span>；</li>
<li><span class="math inline">a_0, a_1, \dots a_{\gcd(n, t) - 1}</span> 一定位于不同轮换。</li>
</ul>
</div></li>
</ul>
<aside class="notes">
<p>两个推论的证明不难（用初等数论就可以解决），大家可以自行思考……</p>
<p>💡 提示：</p>
<ol type="1">
<li><span class="math inline">\because \gcd(n, t) \mid t, \ \therefore \ i + jt \equiv i \pmod {\gcd(n, t)}</span></li>
<li>可看作上一条的推论。</li>
</ol>
</aside>
</section>
<section id="permutation-group" class="slide level2">
<h2>置换群</h2>
<p><span class="math inline">n</span> 个元的所有置换，在复合运算 <span class="math inline">\circ</span> 下成群，称作 <span class="math inline">n</span> 元<strong>对称群 (symmetric group)</strong>，记作 <span class="math inline">S_n</span></p>
<ul>
<li><strong>结合律</strong>：<span class="math inline">(\sigma \circ \tau) \circ \phi = \sigma \circ (\tau \circ \phi)</span></li>
<li><strong>单位元</strong>：恒等置换 <span class="math inline">\epsilon \circ x = x</span>；</li>
<li><strong>逆元</strong>：置换是双射，故必然存在逆置换。</li>
</ul>
<aside class="notes">
<p>对于结合律的进一步说明：等式两边都是 <span class="math inline">\sigma(\tau(\phi(x)))</span></p>
</aside>
</section></section>
<section>
<section id="group-action" class="title-slide slide level1">
<h1>群在集合上的作用</h1>
<p><span class="math display">
\begin{aligned}
\phi: G \times M &amp; \longrightarrow M \\
(\sigma, x) &amp; \longmapsto \sigma \circ x
\end{aligned}
</span></p>
<ul>
<li><span class="math inline">\forall x \in M</span> 满足：
<ul>
<li><strong>单位元</strong>：<span class="math inline">\exist \epsilon \in G \text{ \ s.t. \ }\epsilon \circ x = x</span></li>
<li><strong>结合律</strong>：<span class="math inline">\tau \circ (\sigma \circ x) = (\tau \circ \sigma) \circ x</span></li>
</ul></li>
</ul>
<aside class="notes">
<p><span class="math inline">G</span> 是一个群（这里我们就看成置换群），<span class="math inline">M</span> 是一个集合。如果存在这样的映射 <span class="math inline">\phi</span> 并且满足上述条件，那么我们称群 <span class="math inline">G</span> 在集合 <span class="math inline">M</span> 上有群作用。</p>
<p>根据 Cayley 定理，每个群均同构于某个置换群。有了这个前提可能会更好理解群在集合上的作用。但是今天碍于主题，我们主要探讨置换群对于集合的作用。</p>
</aside>
</section>
<section class="slide level2">

<p>用黑白两色对等边三角形顶点染色，若可通过旋转得到的方案算相同方案，求方案数？</p>
<div class="fragment fade-in-then-out" style="height:0">
<figure>
<img data-src="./assets/ga-example-1.png" class="plain" style="background:transparent" alt="" /><figcaption>在旋转意义下同构</figcaption>
</figure>
</div>
<div class="fragment">
<p><span class="math display">
\begin{aligned}
G&amp; = \{ \text{顺时针旋转 } 0^\circ, 120^\circ, 240^\circ \} \\
M &amp; = \{ \text{不考虑同构时的染色方案} \}
\end{aligned}
</span></p>
</div>
<div class="fragment">
<figure>
<img data-src="./assets/ga-example-2.png" class="plain" style="background:transparent" alt="" /><figcaption>不考虑同构时的染色方案</figcaption>
</figure>
</div>
</section>
<section class="slide level2">

<div class="fragment fade-out" style="height:0" data-fragment-index="1">
<figure>
<img data-src="assets/ga-example-3.png" class="plain" style="background:transparent" alt="" /><figcaption><span class="math inline">G \times M</span></figcaption>
</figure>
</div>
<div class="fragment current-visible" style="height:0" data-fragment-index="1">
<figure>
<img data-src="assets/ga-example-4.png" class="plain" style="background:transparent" alt="" /><figcaption>等价类？</figcaption>
</figure>
</div>
<div class="fragment current-visible" style="height:0" data-fragment-index="2">
<figure>
<img data-src="assets/ga-example-5.png" class="plain" style="background:transparent" alt="" /><figcaption>等价类？</figcaption>
</figure>
</div>
<aside class="notes">
<ul>
<li>图1：
<ul>
<li>可以看到 <span class="math inline">G \times M</span> 后并不会产生新的元素，也就是说 <span class="math inline">G \times M</span> 和 <span class="math inline">M</span> 是一样大的。</li>
<li>存在单位置换（旋转 <span class="math inline">0^\circ</span>）使得它与任何一个染色方案作用都不发生变化；多个旋转作用于染色方案也是满足结合律的。所以这里我们称 <span class="math inline">G</span> 对 <span class="math inline">M</span> 有群作用。</li>
</ul></li>
<li>图2：
<ul>
<li>比如所有置换作用于第二个染色方案，我们实际上得到的就是与第二个方案等价的染色方案，并且我们得到的这些染色方案都是存在于原始集合里面的。</li>
</ul></li>
</ul>
</aside>
</section>
<section class="slide level2">

<p><img data-src="assets/ga-example-6.png" class="plain" style="background:transparent" /></p>
<ul>
<li>一种等价关系？</li>
<li>借助该等价关系对集合进行划分？</li>
<li>有多少不同的等价类？</li>
</ul>
</section>
<section id="orbit" class="slide level2">
<h2>轨道</h2>
<p>群 <span class="math inline">G</span> 作用于集合 <span class="math inline">M</span> 上，<span class="math inline">x \in M</span>，称 <span class="math inline">M</span> 的子集</p>
<p><span class="math display">
\text{orb}_G(x) = \{ \sigma \circ x \mid \sigma \in G \}
</span></p>
<p>为 <span class="math inline">x</span> 在 <span class="math inline">G</span> 作用下的<strong>轨道 (orbit)</strong>，简称过 <span class="math inline">x</span> 的轨道。</p>
<div class="fragment">
<ul>
<li><span class="math inline">G</span> 中置换作用于元素 <span class="math inline">x</span> 所能得到的不同结果；</li>
<li><span class="math inline">|\text{orb}_G(x)|</span>： 对于元素 <span class="math inline">x</span> 而言，<span class="math inline">G</span> 中本质不同置换的种数。</li>
</ul>
</div>
<aside class="notes">
<p>就比如刚刚对三角形着色的例子里，对于第二个染色方案分别用 <span class="math inline">0^\circ, 120^\circ, 240^\circ</span> 的旋转作用于它，便可以得到过它的轨道。</p>
<p>其实本质上就是等价类…… 部分地方记作 <span class="math inline">\mathcal{O}_G(x)</span>，也有的地方直接用等价类的符号 <span class="math inline">[x]</span>。</p>
</aside>
</section>
<section class="slide level2">

<p><span class="math display">
\text{orb}_G(x) = \{ \sigma \circ x \mid \sigma \in G \}
</span></p>
<p><span class="math display">
x \sim y := x \in \text{orb}_G(y)
</span></p>
<ul>
<li><strong>自反性</strong>：<span class="math inline">x \in \text{orb}_G(x)</span>；</li>
<li><strong>对称性</strong>：若 <span class="math inline">y \in \text{orb}_G(x)</span>，则 <span class="math inline">x \in \text{orb}_G(y)</span>；</li>
<li><strong>传递性</strong>：若 <span class="math inline">z \in \text{orb}_G(y), y \in \text{orb}_G(x)</span>，则 <span class="math inline">z \in \text{orb}_G(x)</span>。</li>
</ul>
<aside class="notes">
<p>定义关系 <span class="math inline">x \sim y := x \in \text{orb}_G(y)</span>，那么这是一个等价关系~</p>
<p>💡 提示:</p>
<ol type="1">
<li>既然是置换群，必然有恒等置换；</li>
<li>既然置换群中逆元存在，有能把 x 变成 y 的置换则一定也有能把 y 变成 x 的置换；</li>
<li>既然置换群中的运算封闭，若有置换能使 x -&gt; y，另一置换能使 y -&gt; z，则一定有一个置换能使 x -&gt; z。</li>
</ol>
</aside>
</section>
<section class="slide level2">

<ul>
<li><p>若 <span class="math inline">\text{orb}_G(x) \cap \text{orb}_G(y) \neq \emptyset</span>，则 <span class="math inline">\text{orb}_G(x) = \text{orb}_G(y)</span>；</p></li>
<li><p>在 <span class="math inline">M</span> 的每一条轨道上取一个元素组成 <span class="math inline">M</span> 的一个子集 <span class="math inline">R</span>，称为 <span class="math inline">M</span> 的<strong>轨道的代表元集</strong>，则：</p>
<p><span class="math display">
M = \bigcup\limits_{x \in R} \text{orb}_G(x)
</span></p>
<p>并且此中各 <span class="math inline">\text{orb}_G(x)</span> 互不相交。</p></li>
</ul>
</section>
<section id="stabilizer" class="slide level2">
<h2>稳定子</h2>
<p>设群 <span class="math inline">G</span> 作用于集合 <span class="math inline">M</span>，对 <span class="math inline">x \in M</span>，称</p>
<p><span class="math display">
\text{stab}_G(x) = \{ \sigma \mid \sigma \in G, \sigma \circ x = x \}
</span></p>
<p>为群 <span class="math inline">G</span> 作用下 <span class="math inline">x</span> 的<strong>稳定子 (stabilizer)</strong>。</p>
<div class="fragment">
<ul>
<li>所有作用于 <span class="math inline">x</span> 后结果仍然为 <span class="math inline">x</span> 的置换。</li>
</ul>
</div>
<aside class="notes">
<p>稳定子里面的元素都是置换，集合 <span class="math inline">M</span> 里面某个元素的稳定子包含所有使它不发生变化的置换。</p>
<p>又称固定子群、稳定子群、稳定化子…… 有的地方也写成 <span class="math inline">G_m</span> 或 <span class="math inline">G^m</span>。</p>
</aside>
</section>
<section class="slide level2">

<figure>
<img data-src="assets/ga-example-3.png" class="plain" style="background:transparent" alt="" /><figcaption><span class="math inline">G \times M</span></figcaption>
</figure>
<aside class="notes">
<p>对于第一种和最后一种染色方案而言，其稳定子里面的元素就是三个置换，而对于其他染色方案稳定子都只有一个，就是旋转 <span class="math inline">0^\circ</span> 的置换。</p>
</aside>
</section>
<section class="slide level2">

<p><span class="math display">
\text{stab}_G(x) = \{ \sigma \circ x = x \mid \sigma \in G \} \le G
</span></p>
<div class="fragment">
<ul>
<li><strong>封闭性</strong>：<span class="math inline">\forall \sigma, \tau \in \text{stab}_G(x)</span>，<span class="math inline">\sigma \circ \tau \circ x = \sigma \circ x = x</span>，故 <span class="math inline">(\sigma \circ \tau) \in \text{stab}_G(x)</span>；</li>
<li><strong>结合律</strong>：显然置换的复合满足结合律；</li>
<li><strong>单位元</strong>：恒等置换 <span class="math inline">\epsilon \circ x = x</span>；</li>
<li><strong>逆元</strong>：<span class="math inline">\forall \sigma \in \text{stab}_G(x)</span>，<span class="math inline">\sigma^{-1} \circ x = \sigma^{-1} \circ (\sigma \circ x) = \epsilon(x) = x</span>。</li>
</ul>
</div>
</section>
<section class="slide level2">

<p><span class="math display">
\text{stab}_G(x) = \{ \sigma \circ x = x \mid \sigma \in G \} \le G
</span></p>
<div class="fragment current-visible" style="height:0" data-fragment-index="1">
<ul>
<li>既然是子群，那可以用来对 <span class="math inline">G</span> 进行左陪集划分；</li>
</ul>
</div>
<div class="fragment" data-fragment-index="2">
<ul>
<li><span class="math inline">\beta \text{stab}_G(x)</span> 里的元素相当于作用于 <span class="math inline">x</span> 时 <span class="math inline">G</span> 中所有与 <span class="math inline">\beta</span> 等价的置换：</li>
</ul>
</div>
<div class="fragment current-visible" style="height:0" data-fragment-index="2">
<p><span class="math display">
\beta \text{stab}_G(x) = \{ (\beta \circ \sigma) \circ x = \beta \circ x \mid \sigma \in G \}
</span></p>
</div>
<div class="fragment" data-fragment-index="3">
<p><span class="math display">
\beta \text{stab}_G(x) = \{ \tau \circ x = \beta \circ x \mid \tau \in G \}
</span></p>
</div>
<div class="fragment" data-fragment-index="4">
<p><span class="math display">
|G| = |\text{stab}_G(x)| \cdot [G:\text{stab}_G(x)]
</span></p>
<ul>
<li><span class="math inline">|\text{orb}_G(x)|</span>：对 <span class="math inline">x</span> 而言，<span class="math inline">G</span> 中所有本质不同置换种数。
<ul>
<li>也就是不同的上述陪集的种数！</li>
</ul></li>
</ul>
</div>
</section>
<section id="orbit-stabilizer-theorem" class="slide level2">
<h2>轨道-稳定子定理</h2>
<p>设有限群 <span class="math inline">G</span> 作用于集合 <span class="math inline">M</span> ，<span class="math inline">x \in M</span>，则：</p>
<p><span class="math display">
|G| = \mid \text{stab}_G(x) \mid \cdot \mid \text{orb}_G(x) \mid
</span></p>
</section></section>
<section>
<section id="burnside-lemma" class="title-slide slide level1">
<h1>Burnside 引理</h1>
<p>设有限群 <span class="math inline">G</span> 作用于有限集 <span class="math inline">M</span> 上，则轨道数：</p>
<p><span class="math display">
| M/G | = \frac{1}{|G|} \sum\limits_{\sigma \in G} |\text{fix}(\sigma)|
</span></p>
<p>其中 <span class="math inline">\text{fix}(\sigma)</span> 代表 <span class="math inline">\sigma</span> 的不动元构成的集合：</p>
<p><span class="math display">
\text{fix}(\sigma) = \{ x \mid x \in M, \sigma \circ x = x \}
</span></p>
</section>
<section id="proof-of-burnside-lemma" class="slide level2">
<h2>证明</h2>
<p><span class="math display">
\begin{aligned}
\text{stab}_G(x) &amp; = \{ \sigma \mid \sigma \in G, \sigma \circ x = x \} \\
\text{fix}(\sigma) &amp; = \{ x \mid x \in M, \sigma \circ x = x \}
\end{aligned}
</span></p>
<p><span class="math display">
\sum\limits_{x \in M} \mid \text{stab}_G(x) \mid = \sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid
</span></p>
<aside class="notes">
<p>稳定子是固定 <span class="math inline">x</span> 找 <span class="math inline">\sigma</span>，而不动元是固定 <span class="math inline">\sigma</span> 找 <span class="math inline">m</span>，故对于下面的等式两边本质上只是换了一下遍历的顺序。</p>
</aside>
</section>
<section class="slide level2">

<ul>
<li>每个轨道对轨道数贡献为 <span class="math inline">1</span>，故 <span class="math inline">x \in M</span> 对答案的贡献为 <span class="math inline">\frac{1}{\mid \text{orb}_G(x) \mid}</span>：</li>
</ul>
<p><span class="math display">
  \begin{aligned}
  | M/G | 
  &amp; = \sum\limits_{x \in M} \frac{1}{ \mid \text{orb}_G(x) \mid } \\
  &amp; = \sum\limits_{x \in M}\frac{ \mid \text{stab}_G(x) \mid }{ |G| } \text{（轨道-稳定子定理）} \\
  &amp; = \frac{1}{|G|}\sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid
  \end{aligned}
</span></p>
</section>
<section class="slide level2">

<p>对正六边形的 <span class="math inline">6</span> 个顶点，一半涂黑一半涂白。若经旋转可得到的方案算相同方案，求方案数？</p>
<div class="fragment">
<p><span class="math display">
M = \{ \text{不计同构的涂色方案} \} \enspace |M| = \binom{6}{3} = 20
</span></p>
<p><span class="math display">
G = \{ \text{顺时针旋转} 0^\circ, 60^\circ, 120^\circ, 180^\circ, 240^\circ, 300^\circ \} \\
</span></p>
<p>记 <span class="math inline">6</span> 个顶点分别为 <span class="math inline">A_1, A_2, \dots, A_6</span></p>
</div>
</section>
<section class="slide level2">

<h3 id="旋转-0circ">旋转 <span class="math inline">0^\circ</span></h3>
<p><span class="math display">
\left(\begin{array}{c} 
A_1 &amp; A_2 &amp; A_3 &amp; A_4 &amp; A_5 &amp; A_6 \\ 
A_1 &amp; A_2 &amp; A_3 &amp; A_4 &amp; A_5 &amp; A_6 
\end{array}\right)
</span></p>
<p>将这一置换作用于 <span class="math inline">M</span> 中的任意元素都不会使该元素发生变化，故不动元有 <span class="math inline">20</span> 个。</p>
</section>
<section class="slide level2">

<h3 id="旋转-60circ">旋转 <span class="math inline">60^\circ</span></h3>
<p><span class="math display">
\left(\begin{array}{c} 
A_1 &amp; A_2 &amp; A_3 &amp; A_4 &amp; A_5 &amp; A_6 \\ 
A_6 &amp; A_1 &amp; A_2 &amp; A_3 &amp; A_4 &amp; A_5 
\end{array}\right)
</span></p>
<p>若要成为不动元，则应当满足：</p>
<p><span class="math display">
A_1 = A_2 = \dots = A_6
</span></p>
<p>故没有不动元</p>
</section>
<section class="slide level2">

<h3 id="旋转-120circ">旋转 <span class="math inline">120^\circ</span></h3>
<p><span class="math display">
\left(\begin{array}{c} 
A_1 &amp; A_2 &amp; A_3 &amp; A_4 &amp; A_5 &amp; A_6 \\ 
A_5 &amp; A_6 &amp; A_1 &amp; A_2 &amp; A_3 &amp; A_4 
\end{array}\right)
</span></p>
<p>若要成为不动元，则应当满足：</p>
<p><span class="math display">
A_1 = A_3 = A_5, \ A_2 = A_4 = A_6
</span></p>
<p>故不动元数量为 <span class="math inline">2</span></p>
</section>
<section class="slide level2">

<h3 id="旋转-180circ">旋转 <span class="math inline">180^\circ</span></h3>
<p><span class="math display">
\left(\begin{array}{c} 
A_1 &amp; A_2 &amp; A_3 &amp; A_4 &amp; A_5 &amp; A_6 \\ 
A_4 &amp; A_5 &amp; A_6 &amp; A_1 &amp; A_2 &amp; A_3 
\end{array}\right)
</span></p>
<p>若要成为不动元，则应当满足：</p>
<p><span class="math display">
A_1 = A_4, \ A_2 = A_5, \ A_3 = A_6
</span></p>
<p>故没有不动元</p>
</section>
<section class="slide level2">

<ul>
<li>旋转 <span class="math inline">60^\circ</span> 与 旋转 <span class="math inline">300^\circ</span> 情形相似；</li>
<li>旋转 <span class="math inline">120^\circ</span> 与 旋转 <span class="math inline">240^\circ</span> 情形相似。</li>
</ul>
<p>轨道数：<span class="math inline">\frac{1}{6}(20 + 2 + 2) = 4</span></p>
</section></section>
<section id="polya-enumeration-theorem" class="title-slide slide level1">
<h1>Pólya 计数定理</h1>
<ul>
<li><p>将置换表示为若干轮换乘积，若轮换内元素颜色均相同即为不动元（这样才能保证每一个点变成新点后的颜色与原先一致）；</p></li>
<li><p>记染色可选的颜色数为 <span class="math inline">m</span>， <span class="math inline">c(\sigma)</span> 为置换 <span class="math inline">\sigma</span> 被分解为不交轮换乘积的个数，则：</p>
<div class="fragment current-visible" style="height:0">
<p><span class="math display">
\text{fix}(\sigma) = m^{c(\sigma)}
</span></p>
</div>
<div class="fragment">
<p><span class="math display">
| M/G | = \frac{1}{|G|} \sum\limits_{\sigma \in G} m^{c(\sigma)}
</span></p>
</div></li>
</ul>
<aside class="notes">
<p>前面讲到了置换 <span class="math inline">\sigma</span> 可以被拆成若干个长度相等的映射链，也就是若干个大小相等的轮换。考虑在原始的（不考虑同构）的染色方案集合里，什么样的元素会成为置换 <span class="math inline">\sigma</span> 的下的不动元？</p>
<p>是不是只要每个轮换内的点我染的颜色都一样，那么是不是就成为不动元了…… 那么根据乘法原理就可以得到 Pólya 计数定理了。</p>
</aside>
</section>

<section id="a-breif-summary" class="title-slide slide level1">
<h1>小结</h1>
<ul>
<li><a href="#/relation">关系</a> | <a href="#/equivalence-relation">等价关系</a> | <a href="#/equivalence-class">等价类</a>
<ul>
<li>对集合分类：等价类 <span class="math inline">[a]</span> 内的元素都与存在 <span class="math inline">a</span> 等价关系；</li>
</ul></li>
<li><a href="#/group">群</a> | <a href="#/subgroup">子群</a> | <a href="#/coset">陪集</a>
<ul>
<li>对群分类：陪集 <span class="math inline">gH</span> 里的所有元素都与 <span class="math inline">g</span> 存在等价关系；</li>
</ul></li>
<li><a href="#/group-action">群在集合上的作用</a>
<ul>
<li><a href="#/orbit">轨道</a>：<span class="math inline">M</span> 的子集，在 <span class="math inline">G</span> 作用下与 <span class="math inline">x</span> 等价的元素；</li>
<li><a href="#/stabilizer">稳定子</a>：<span class="math inline">G</span> 的子群，对于 <span class="math inline">x</span> 而言 <span class="math inline">G</span> 中等价的置换；</li>
<li><a href="#/orbit-stabilizer-theorem">轨道-稳定子定理</a> | <a href="#/burnside-lemma">Burnside 引理</a> | <a href="#/polya-enumeration-theorem">Pólya 计数法</a></li>
</ul></li>
</ul>
</section>

<section>
<section id="coloring-necklace" class="title-slide slide level1">
<h1>项链染色</h1>
<p>长为 <span class="math inline">n</span> 的环，<span class="math inline">m</span> 种颜色对环上元素染色，经旋转或翻转都算作相同方案</p>
<p><span class="math inline">n, m \le 10^9</span></p>
<aside class="notes">
<p>这里将之前对多边形顶点染色问题一般化。</p>
</aside>
</section>
<section id="cn-analysis" class="slide level2">
<h2>分析</h2>
<p><span class="math display">
\begin{aligned}
G &amp; = \{ \text{顺时针旋转} \frac{2\pi}{n}, \dots, (n - 1)\frac{2\pi}{n}, 2\pi, \\
&amp; \text{过每一条对称轴的翻转 } \} \\
M &amp; = \{ \text{不考虑同构的所有染色方案}  \}
\end{aligned}
</span></p>
<p><span class="math inline">G</span> 作用于 <span class="math inline">M</span></p>
<div class="fragment">
<p><span class="math inline">G</span> 中复合运算封闭吗？</p>
</div>
</section>
<section class="slide level2">

<p>若将环上的元素按顺时针编号：<span class="math inline">0, 1, \dots (n - 1)</span></p>
<ul>
<li>顺时针旋转 <span class="math inline">k \frac{2\pi}{n}</span>：<span class="math inline">\sigma_k(i) = (i + k) \bmod n</span>；</li>
<li>沿过点 <span class="math inline">a</span> 的对称轴翻转： <span class="math display">
\tau_a(i) =
\begin{cases}
i &amp; i = a \text{ \ or \ } a \text{ 对面的点 } \\
(2a - i) \bmod n &amp; \text{ otherwise } 
\end{cases}
</span></li>
</ul>
<div class="fragment current-visible" style="height:0">
<ul>
<li>注：若 <span class="math inline">n</span> 为偶数，则翻转对称轴可能同时过两条边的中点。这等同于共有 <span class="math inline">2n</span> 个点且不考虑此类对称轴的情况，故下面暂不考虑这种对称轴。</li>
</ul>
</div>
<div class="fragment current-visible" style="height:0">
<ul>
<li>考虑 <span class="math inline">i \neq a</span> 的情况（<span class="math inline">i = a</span> 显然封闭），若 <span class="math inline">2 \mid k</span>： <span class="math display">
\sigma_k \circ \tau_a \circ i = (2a - i + k) \bmod n = \tau_{(a + \frac{k}{2}) \bmod n}
</span></li>
</ul>
</div>
<div class="fragment">
<ul>
<li>考虑 <span class="math inline">i \neq a</span> 的情况（<span class="math inline">i = a</span> 显然封闭），若 <span class="math inline">2 \nmid k</span>： <span class="math display">
\sigma_k \circ \tau_a \circ i = (2a - i + k) \bmod n = \tau_{(a + \frac{n + k}{2}) \bmod n}
</span></li>
</ul>
</div>
<aside class="notes">
<p><span class="math inline">n</span> 为偶数时，对称轴过两个点；而 <span class="math inline">n</span> 为奇数时，对称轴过一个点和一条边。</p>
<p>另外 对于 <span class="math inline">n</span> 为偶数时，由于对称轴可以同时过两条边，因此考虑的时候不妨在每条边中间再加一个点，即考虑 <span class="math inline">2n</span> 个点围成的环只过点的对称轴…… （因为上面只说明了过点的对称轴，所以不妨这么理解qwq）。</p>
<p>可能有点不严密，大家自己推一推应该也能发现是正确的（逃</p>
</aside>
</section>
<section id="cn-rotation" class="slide level2">
<h2>旋转</h2>
<ul>
<li>旋转置换一共 <span class="math inline">n</span> 种；</li>
<li>旋转 <span class="math inline">\frac{2\pi}{n}</span> 时只能分解成一个不交轮换；</li>
<li>旋转 <span class="math inline">i \frac{2\pi}{n}</span> 可看作前者的 <span class="math inline">i</span> 次幂，故可拆成 <span class="math inline">\gcd(n, i)</span> 个轮换：</li>
</ul>
<p><span class="math display">
\sum\limits_{\sigma} \mid \text{fix}(\sigma) \mid = \sum\limits_{i = 1}^{n} m^{\gcd(n, i)}
</span></p>
<aside class="notes">
<p>旋转 <span class="math inline">\frac{2\pi}{n}</span> 时显然只能拆成一个轮换。回忆前面关于快速求轮换幂的相关内容。</p>
<p>然而现在复杂度是 <span class="math inline">\mathcal{O}(N)</span> 的，需要借助数论知识进一步优化……</p>
</aside>
</section>
<section class="slide level2">

<p><span class="math display">
\begin{aligned}
\sum\limits_{g \in G} \mid \text{fix}(\sigma) \mid 
&amp; = \sum\limits_{i = 1}^{n} m^{\gcd(n, i)} \\
&amp; = \sum\limits_{d \mid n} m^d \sum\limits_{i = 1}^{n} [ \gcd(n, i) = d ] \\
&amp; =\sum\limits_{d \mid n} m^d \sum\limits_{i = 1}^{\frac{n}{d}} [ \gcd(\frac{n}{d}, i) = 1 ] \\
&amp; = \sum\limits_{d \mid n} m^d \cdot \varphi(\frac{n}{d})
\end{aligned}
</span></p>
</section>
<section id="cn-flipping" class="slide level2">
<h2>翻转</h2>
<ul>
<li>翻转置换一共 <span class="math inline">n</span> 种。</li>
<li><span class="math inline">n</span> 为偶数：
<ul>
<li><span class="math inline">\frac{n}{2}</span> 条过点的对称轴：<span class="math inline">c(\tau) = \frac{n}{2} + 1</span></li>
<li><span class="math inline">\frac{n}{2}</span> 条过边的对称轴：<span class="math inline">c(\tau) = \frac{n}{2}</span> <span class="math display">
\sum\limits_{\tau} \mid \text{fix}(\tau) \mid 
= \frac{n}{2} \cdot m^{\frac{n}{2} + 1} + \frac{n}{2} \cdot m^{\frac{n}{2}} 
</span></li>
</ul></li>
</ul>
</section>
<section class="slide level2">

<ul>
<li><span class="math inline">n</span> 为奇数：
<ul>
<li><span class="math inline">n</span> 条 既过点又过边的对称轴：<span class="math inline">c(\tau) = \frac{n + 1}{2}</span></li>
</ul>
<span class="math display">
\sum\limits_{\tau} \mid \text{fix}(\tau) \mid 
= n \cdot m^{\frac{n + 1}{2}}
</span></li>
</ul>
</section>
<section id="cn-finale" class="slide level2">
<h2>结论</h2>
<p><span class="math display">
\begin{aligned}
| M/G | &amp; = \frac{\sum\limits_{\sigma} \mid \text{fix}(\sigma) \mid + \sum\limits_{\tau} \mid \text{fix}(\tau) \mid}{2n} \\
&amp; = \frac{1}{2n}\sum\limits_{d \mid n} m^d \cdot \varphi(\frac{n}{d}) \\
&amp; + \frac{1}{2n} \begin{cases}
\frac{n}{2} \cdot m^{\frac{n}{2} + 1} + \frac{n}{2} \cdot m^{\frac{n}{2}} &amp; 2 \mid n \\
n \cdot m^{\frac{n + 1}{2}} &amp; 2 \nmid n
\end{cases}
\end{aligned}
</span></p>
<p>复杂度：<span class="math inline">\mathcal{O}(d(n) \cdot \sqrt{n})</span>，<span class="math inline">d(n)</span> 代表 <span class="math inline">n</span> 的约数个数。</p>
</section></section>
<section>
<section id="icpc-2019-nanchang-j" class="title-slide slide level1">
<h1>南昌 J. Summon</h1>
<p>现要从 <span class="math inline">4</span> 种不同的水晶中取 <span class="math inline">n</span> 个围成一个圈，但有 <span class="math inline">m</span> 个限制条件：每条限制条件要求某四种水晶不能在围成的圈中连续出现。通过旋转可互相得到的方案算作一种方案，问有多少种本质不同的方案？（结果模 <span class="math inline">998244353</span>）</p>
<p><span class="math inline">n \le 10^5, m \le 256</span></p>
<aside class="notes">
<p>这其实是去年老刘专题里面一道题的稍微加强版…… 原题是要求某两种不能连续，这里改成了某四种……（POJ 2888）</p>
</aside>
</section>
<section id="ncj-analysis" class="slide level2">
<h2>分析</h2>
<p><span class="math display">
\begin{aligned}
G &amp; = \{ \text{顺时针旋转} \frac{2\pi}{n}, \dots, (n - 1)\frac{2\pi}{n}, 2\pi \} \\
M &amp; = \{ \text{满足限制且不计同构的染色方案} \}
\end{aligned}
</span></p>
<div class="fragment">
<ul>
<li>单单把每一个轮换内的所有元素染成相同颜色可能破坏限制条件；</li>
<li>无法直接应用 Pólya 计数定理。</li>
</ul>
</div>
<aside class="notes">
<p>之前说 Pólya 计数定理的时候，我们是基于同一个轮换内的所有元素都染色成同一个颜色得出的。在这道题目里，不动元不仅要满足轮换内元素颜色相等，同时在这一前提下还要满足限制条件。我们虽然没有办法直接套用 Pólya，但是只要能够求出不动点借助 Burnside 引理还是能够解决问题的……</p>
</aside>
</section>
<section class="slide level2">

<ul>
<li>旋转 <span class="math inline">\frac{2\pi}{n}</span> 只能分解成一个不交轮换；</li>
<li>旋转 <span class="math inline">i \frac{2\pi}{n}</span> 可看作前者的 <span class="math inline">i</span> 次幂，因此：
<ul>
<li>可表示为 <span class="math inline">\gcd(n, i)</span> 个不交轮换之积；</li>
<li>标号模 <span class="math inline">\gcd(n, i)</span> 结果相同的点在同一轮换内。</li>
</ul></li>
</ul>
<div class="fragment">
<p><strong>对于旋转 <span class="math inline">i \frac{2\pi}{n}</span> 这一置换，只需确定前 <span class="math inline">\gcd(n, i)</span> 个元素的颜色即可知道该置换下不动元数量！</strong></p>
</div>
<aside class="notes">
<p>换句话说，前 <span class="math inline">\gcd(n, i)</span> 个元素一定是位于不同轮换内的。对于不动点而言，既然同一轮换内染色方案一致，那么整个染色方案完全就是由前 <span class="math inline">\gcd(n, i)</span> 个元素一直往后复制这样生成的（逃</p>
<p>可以考虑 DP。</p>
</aside>
</section>
<section id="ncj-dp" class="slide level2">
<h2>DP 求不动元数量</h2>
<ul>
<li>记 <span class="math inline">\text{v} \langle a, b, c, d \rangle</span> 代表是否允许 <span class="math inline">a, b, c, d</span> 四种颜色相邻；</li>
</ul>
<p><span class="math display">
\text{v} \langle a, b, c, d \rangle =
\begin{cases}
0 &amp; \text{不允许 } a, b, c, d \text{ 相邻} \\
1 &amp; \text{允许 } a, b, c, d \text{ 相邻}
\end{cases}
</span></p>
</section>
<section class="slide level2">

<ul>
<li>记 <span class="math inline">\text{dp} \langle i, a, b, c \rangle</span> 代表 <span class="math inline">i</span> 个元素排成一排，最后 <span class="math inline">3</span> 个元素的颜色分别为 <span class="math inline">a, b, c</span> 的方案数： <span class="math display">
\text{dp} \langle i, a, b, c \rangle = \sum\limits_{k} \text{v} \langle k, a, b, c \rangle \cdot \text{dp} \langle i - 1, k, a, b \rangle
</span></li>
</ul>
<div class="fragment">
<ul>
<li>枚举前 <span class="math inline">3</span> 个元素的颜色 <span class="math inline">\langle a, b, c \rangle</span>：
<ul>
<li>只初始化 <span class="math inline">\text{dp} \langle 3, a, b, c \rangle = 1</span>；</li>
<li><span class="math inline">\text{dp} \langle m + 3, a, b, c \rangle</span> 即为 <span class="math inline">m</span> 个元素围成环时不动元方案数。</li>
</ul></li>
</ul>
</div>
<aside class="notes">
<p>对于环上的问题不方便考虑的话不妨先拆成链上的问题考虑（就不用考虑首尾是否满足条件）……</p>
<p>最后要考虑首尾的情况的时候，不妨在尾多 DP 三个元素，然后只取首三个元素与末三个元素相同的方案。</p>
<p>这样做一次 DP 复杂度是 <span class="math inline">\mathcal{O}(64^3 N)</span> 的…… 而且对于每一种置换都要做一次…… 显然复杂度不可以接受。</p>
<p>看看能不能用矩阵快速幂优化。</p>
</aside>
</section>
<section id="ncj-matrix-fastpow" class="slide level2">
<h2>矩阵快速幂优化 DP</h2>
<p><span class="math display">
  \text{dp} \langle i, a, b, c \rangle = \sum\limits_{k} \text{v} \langle k, a, b, c \rangle \cdot \text{dp} \langle i - 1, k, a, b \rangle
</span></p>
<p><span class="math display">
\begin{aligned}
  \begin{bmatrix}
    \text{dp} \langle i, 1, 1, 1 \rangle \\
    \text{dp} \langle i, 1, 1, 2 \rangle \\
    \vdots \\
    \text{dp} \langle i, 4, 4, 4 \rangle
  \end{bmatrix}
\end{aligned}
= T \cdot
\begin{aligned}
  \begin{bmatrix}
    \text{dp} \langle i - 1, 1, 1, 1 \rangle \\
    \text{dp} \langle i - 1, 1, 1, 2 \rangle \\
    \vdots \\
    \text{dp} \langle i - 1, 4, 4, 4 \rangle
  \end{bmatrix}
\end{aligned}
</span></p>
<div class="fragment current-visible" style="height:0">
<p><span class="math display">
\text{dp} \langle i, a, b, c \rangle = \sum\limits_{\langle j, k, l \rangle} T[a, b, c][j, k, l] \cdot \text{dp} \langle i - 1, j, k, l \rangle
</span></p>
</div>
<div class="fragment">
<p><span class="math display">
T[ a, b, c ][ k, a, b ] = \text{v} \langle k, a, b, c \rangle
</span></p>
</div>
<aside class="notes">
<p>可以把后三个连续颜色 <span class="math inline">&lt;a, b, c&gt;</span> 看出一个可以用 <span class="math inline">0 \sim 63</span> 表示的一个状态，就更好理解了……</p>
<p><span class="math inline">T</span> 中其余元素都是 <span class="math inline">0</span>。</p>
</aside>
</section>
<section class="slide level2">

<ul>
<li>枚举前三 <span class="math inline">3</span> 个元素的颜色 <span class="math inline">\langle a, b, c \rangle</span> 时，初始化： <span class="math display">
\begin{aligned}
\begin{bmatrix}
  1 \\
  0 \\
  \vdots \\
  0
\end{bmatrix}
\end{aligned},
\begin{aligned}
\begin{bmatrix}
  0 \\
  1 \\
  \vdots \\
  0
\end{bmatrix}
\end{aligned},
\dots, 
\begin{aligned}
\begin{bmatrix}
  0 \\
  0 \\
  \vdots \\
  1
\end{bmatrix}
\end{aligned}
</span></li>
<li>等价于 <span class="math inline">T^{n}</span> 直接乘上单位矩阵；</li>
<li><span class="math inline">T^{n}</span> 主对角线元素之和即为所有不动元数量。</li>
</ul>
<aside class="notes">
<p>置换 <span class="math inline">\sigma</span> 下不动元的个数只跟其能被分解成不交轮换乘积的轮换个数有关。</p>
</aside>
</section>
<section id="ncj-finale" class="slide level2">
<h2>结论</h2>
<div class="fragment fade-out" data-fragment-index="1" style="height:0">
<ul>
<li>记 <span class="math inline">T^i</span> 对角线元素之和为 <span class="math inline">f(i)</span></li>
<li>旋转 <span class="math inline">i \frac{2\pi}{n}</span> 下不动元个数为 <span class="math inline">f(\gcd(n, i))</span></li>
</ul>
</div>
<div class="fragment" data-fragment-index="1">
<p><span class="math display">
\begin{aligned}
\sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid 
&amp; = \sum\limits_{i = 1}^{n} f(\gcd(n, i)) \\
&amp; = \sum\limits_{d \mid n} f(d) \cdot \sum\limits_{i = 1}^{n} [\gcd(n, i) = d] \\
&amp; = \sum\limits_{d \mid n} f(d) \cdot \varphi(\frac{n}{d})
\end{aligned}
</span></p>
<ul>
<li>复杂度： <span class="math inline">\mathcal{O}(d(n) \cdot 64^3\log{n})</span>，其中 <span class="math inline">d(n)</span> 代表 <span class="math inline">n</span> 的约数个数。</li>
</ul>
</div>
</section></section>
<section>
<section id="coloring-undirected-graph" class="title-slide slide level1">
<h1>无向图同构计数</h1>
<p><span class="math inline">n</span> 个点无向完全图，<span class="math inline">m</span> 种颜色给边染色，求本质不同的染色方案数。</p>
<p><span class="math inline">n \le 60, \ m \le 10^3</span></p>
<div class="fragment">
<ul>
<li>两张图若<strong>对点重标号</strong>后可以重合即为同构；</li>
<li>把边的不存在当作一种颜色可将其推广至一般无向图同构。</li>
</ul>
</div>
</section>
<section id="cug-analysis" class="slide level2">
<h2>分析</h2>
<p><span class="math display">
\begin{aligned}
G &amp; = S_n \enspace (n \text{阶对称群}), \ \mid S_n \mid = n! \\
M &amp; = \{ \text{不计同构的无向图染色方案} \}
\end{aligned}
</span></p>
<ul>
<li>置换是对点的置换，而染色是对边染色；</li>
<li>两点确定一条边，分析边两端点的情况。</li>
</ul>
<aside class="notes">
<p>根据无向图同构的定义发现对于边的置换非常难找…… 要想办法把对点的置换与边的置换联系起来…… 既然两点可以确定一条边，那不妨分析边两边的情况。</p>
<p>后面会用类似 “点置换”、“点轮换” 和 “边置换”、“边轮换” 等用词对两者进行区分。</p>
</aside>
</section>
<section id="cug-edge-case-1" class="slide level2">
<h2>两端在同一轮换内的边</h2>
<p><span class="math display">
\sigma = (1 \enspace 3 \enspace 5 \enspace 6) \cdot (2 \enspace 4)
</span></p>
<div class="fragment current-visible" style="height:0">
<ul>
<li>对于两端点位于同一点轮换内的边：
<ul>
<li><span class="math inline">\langle 1, 3 \rangle \rightarrow \langle 3 ,5 \rangle \rightarrow \langle 5, 6 \rangle \rightarrow \langle 6, 1 \rangle</span></li>
<li><span class="math inline">\langle 1, 5 \rangle \rightarrow \langle 3, 6 \rangle</span></li>
<li><span class="math inline">\langle 2, 4 \rangle</span></li>
</ul></li>
</ul>
</div>
</section>
<section class="slide level2">

<p><span class="math display">
(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1})
</span></p>
<p><span class="math display">
\langle a_i, a_j \rangle \rightarrow \langle a_{(i + 1) \bmod l}, a_{(j + 1) \bmod l} \rangle \rightarrow \dots
</span></p>
<div class="fragment current-visible" style="height:0">
<p><span class="math display">
\begin{cases}
i + t \equiv i \pmod l \\
j + t \equiv j \pmod l
\end{cases}
</span></p>
</div>
<div class="fragment">
<p><span class="math display">
t \equiv 0 \pmod l
</span></p>
<p>最小正整数解 <span class="math inline">t = l</span>，则边轮换长度至多为 <span class="math inline">l</span>。</p>
</div>
</section>
<section class="slide level2">

<p><span class="math display">
(a_0 \enspace a_1 \enspace \dots \enspace a_{l  - 1})
</span></p>
<p><span class="math display">
\langle a_i, a_j \rangle \rightarrow \langle a_{(i + 1) \bmod l}, a_{(j + 1) \bmod l} \rangle \rightarrow \dots
</span></p>
<div class="fragment current-visible" style="height:0">
<p><span class="math display">
\begin{cases}
i + t \equiv j \pmod l \\
j + t \equiv i \pmod l
\end{cases}
</span></p>
</div>
<div class="fragment">
<p><span class="math display">
2i \equiv 2j \pmod l
</span></p>
<ul>
<li>若 <span class="math inline">2 \nmid l</span>，则 <span class="math inline">i \equiv j \pmod l</span>，无法构成边；</li>
<li>若 <span class="math inline">2 \mid l</span>，则 <span class="math inline">i \equiv j \pmod {\frac{l}{2}}</span>，最小非负 <span class="math inline">t = \frac{l}{2}</span>。</li>
</ul>
</div>
<aside class="notes">
<p>下标间距相同的边必然在同一边轮换内。</p>
</aside>
</section>
<section class="slide level2">

<p><span class="math display">
(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1})
</span></p>
<ul>
<li>对于边 <span class="math inline">\langle a_i, a_j \rangle</span> 所在的边轮换：
<ul>
<li>若 <span class="math inline">2 \mid l</span> 且 <span class="math inline">\mid j - i \mid = \frac{l}{2}</span>，则其大小为 <span class="math inline">\frac{l}{2}</span>；</li>
<li>否则其大小为 <span class="math inline">l</span>；</li>
</ul></li>
<li><span class="math inline">\mid j - i \mid \bmod l</span> 相同的边在同一边轮换内，故边轮换个数为 <span class="math inline">\lfloor \frac{l}{2} \rfloor</span>。</li>
</ul>
<aside class="notes">
<p>换句话说：</p>
<ul>
<li>两点在相同且大小为 <span class="math inline">l</span> 的点轮换里的边共可构成 <span class="math inline">\lfloor \frac{l}{2} \rfloor</span> 个边轮换，其中：
<ul>
<li>若 <span class="math inline">2 \nmid l</span>，则每个边轮换大小均为 <span class="math inline">l</span>；</li>
<li>若 <span class="math inline">2 \mid l</span>，则一个边轮换大小为 <span class="math inline">\frac{l}{2}</span>，其余边轮换大小为 <span class="math inline">l</span>。</li>
</ul></li>
</ul>
</aside>
</section>
<section id="cug-edge-case-2" class="slide level2">
<h2>两端在不同轮换内的边</h2>
<p><span class="math display">
\sigma = (1 \enspace 3 \enspace 5 \enspace 6) \cdot (2 \enspace 4)
</span></p>
<ul>
<li>两点在不同点轮换里的边：
<ul>
<li><span class="math inline">\langle 1, 2 \rangle \rightarrow \langle 3, 4 \rangle \rightarrow \langle 5, 2 \rangle \rightarrow \langle 6, 4 \rangle</span></li>
<li><span class="math inline">\langle 1, 4 \rangle \rightarrow \langle 3, 2 \rangle \rightarrow \langle 5, 4 \rangle \rightarrow \langle 6, 2 \rangle</span></li>
</ul></li>
</ul>
</section>
<section class="slide level2">

<p><span class="math display">
(a_0 \enspace a_1 \enspace \dots \enspace a_{l - 1}) \cdot (b_0 \enspace b_1 \enspace \dots \enspace b_{s - 1} )
</span></p>
<p><span class="math display">
\langle a_i, b_j \rangle \rightarrow \langle a_{(i + 1) \bmod l}, b_{(j + 1) \bmod s} \rangle \rightarrow \dots
</span></p>
<div class="fragment">
<p><span class="math display">
\begin{cases}
i + t \equiv i \pmod l \\
j + t \equiv j \pmod s
\end{cases}
</span></p>
<ul>
<li>每个边轮换大小为 <span class="math inline">\text{lcm}(l, s)</span>，共 <span class="math inline">\frac{ls}{\text{lcm}(l, s)} = \gcd(l, s)</span> 个。</li>
</ul>
</div>
</section>
<section id="cug-vertex-edge-relation" class="slide level2">
<h2>点轮换与边轮换的关系</h2>
<p><span class="math display">
\sigma = \prod\limits_{i = 1}^{k} c_i \quad (\text{轮换 } c_i \text{ 长度为 } l_i)
</span></p>
<ul>
<li>可表示成边轮换的个数： <span class="math display">
\sum\limits_{i = 1}^{k} \left\lfloor \frac{l_i}{2} \right\rfloor + \sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k} \gcd(l_i, l_j)
</span></li>
</ul>
<div class="fragment current-visible" style="height:0">
<ul>
<li>不动元？每个边轮换内的边染色情况应当相同；</li>
<li><span class="math inline">\mid S_n \mid = n!</span>，没办法枚举每一个置换……</li>
</ul>
</div>
<div class="fragment">
<ul>
<li>边轮换的个数只跟每个点轮换的大小有关系；</li>
<li>枚举点轮换大小的情况（<span class="math inline">n</span> 的拆分方案）？</li>
</ul>
</div>
<aside class="notes">
<p>想办法剪枝。我们并不关系每个边置换里面有哪些边或者有多少边…… 既然每个边轮换内的边颜色都要一样，我们只关心边轮换的个数就行了。</p>
</aside>
</section>
<section id="cug-pruning" class="slide level2">
<h2>剪枝</h2>
<ul>
<li><p>枚举 <span class="math inline">n</span> 的拆分方案：</p>
<p><span class="math display">
n = \sum\limits_{i = 1}^{k} l_i \ (l_1 \le l_2 \le \dots \le l_k)
</span></p></li>
<li><p>每一种拆分方案对应多少点置换？</p></li>
</ul>
</section>
<section class="slide level2">

<div class="fragment fade-out" data-fragment-index="1" style="height:0">
<ul>
<li><span class="math inline">n</span> 个点分配到轮换内（多重组合数）： <span class="math display">
\frac{n!}{\prod\limits_{i = 1}^{k} l_i!}
</span></li>
</ul>
</div>
<div class="fragment current-visible" data-fragment-index="1" style="height:0">
<ul>
<li>再考虑轮换内的顺序（圆排列）：
<ul>
<li>比如 <span class="math inline">(1 \enspace 2 \enspace 3)</span> 和 <span class="math inline">(1 \enspace 3 \enspace 2)</span> 算不同的置换 <span class="math display">
\frac{n!}{\prod\limits_{i = 1}^{k} l_i!} \cdot \prod\limits_{i = 1}^{k} (l_i - 1)!
</span></li>
</ul></li>
</ul>
</div>
<div class="fragment">
<ul>
<li>对于长度相等的轮换，其之间的顺序不计。
<ul>
<li>记共有 <span class="math inline">s</span> 种不同长度的轮换，其中第 <span class="math inline">i</span> 种轮换的个数为 <span class="math inline">q_i</span>，则： <span class="math display">
\frac{n!}{\prod\limits_{i = 1}^{k} l_i} \cdot \prod\limits_{i = 1}^{s} \frac{1}{q_i!}
</span></li>
</ul></li>
</ul>
</div>
</section>
<section id="ucg-finale" class="slide level2">
<h2>结论</h2>
<ul>
<li>对 <span class="math inline">n</span> 的每一种拆分方案：<span class="math inline">n = \sum\limits_{i = 1}^{k} l_i</span>
<ul>
<li><span class="math inline">l_1 \le l_2 \le \dots \le l_k</span>；</li>
<li>记共有 <span class="math inline">s</span> 种不同长度的轮换，其中第 <span class="math inline">i</span> 种轮换的个数为 <span class="math inline">q_i</span>；</li>
<li>其对应的点轮换数量为：</li>
</ul></li>
</ul>
<p><span class="math display">
\frac{n!}{(\prod\limits_{i = 1}^{k} l_i) \cdot (\prod\limits_{i = 1}^{s} q_i!)}
</span></p>
</section>
<section class="slide level2">

<p><span class="math display">
\begin{aligned}
&amp; \frac{1}{|G|} \sum\limits_{\sigma \in G} \mid \text{fix}(\sigma) \mid \\
&amp; = \frac{1}{n!} \cdot \sum\frac{n!}{(\prod\limits_{i = 1}^{k} l_i) \cdot (\prod\limits_{i = 1}^{s} q_i!)} \cdot m^{\sum\limits_{i = 1}^{k} \left\lfloor \frac{l_i}{2} \right\rfloor + \sum\limits_{i = 1}^{k}\sum\limits_{j = i + 1}^{k} \gcd(l_i, l_j)}
\end{aligned}
</span></p>
<ul>
<li>复杂度 <span class="math inline">\mathcal{O} \left( \sum\limits_{p \in \text{Partition}(n)} \text{len}^2(p) \cdot \log{n} \right)</span></li>
<li>其实题目数据范围内 <span class="math inline">\text{Partition}(n)</span> 大小不大…… 所以 <span class="math inline">\mathcal{O}(\text{能过})</span>。</li>
</ul>
<aside class="notes">
<p><span class="math inline">\text{Partition}(n)</span> 指 <span class="math inline">n</span> 的拆分方案数，而 <span class="math inline">\text{len}(p)</span> 指拆分方案 <span class="math inline">p</span> 的长度（即拆成了多少个点轮换）</p>
</aside>
</section>
<section class="slide level2">

<h3 id="思路回顾">思路回顾</h3>
<ul>
<li>置换是对点的置换，均可分解成点轮换之积；</li>
<li>染色对边染色，同一边轮换内边染色方案相同；</li>
<li>点轮换和边轮换之间的关系？</li>
<li>只关心边轮换个数，其只与点轮换的大小情况有关，枚举点轮换的大小情况……</li>
</ul>
</section></section>
<section>
<section id="finale" class="title-slide slide level1">
<h1>谢谢大家</h1>

</section>
<section id="probset-1" class="slide level2">
<h2>相关题目 #1</h2>
<ul>
<li><a href="http://acm.hdu.edu.cn/showproblem.php?pid=1817">HDU 1817: Necklace of Beads</a></li>
<li><a href="http://acm.hdu.edu.cn/showproblem.php?pid=3547">HDU 3547: DIY Cube</a></li>
<li><a href="http://acm.hdu.edu.cn/showproblem.php?pid=3441">HDU 3441: Rotation</a></li>
<li><a href="http://poj.org/problem?id=2888">POJ 2888: Magic Bracelet</a></li>
<li><a href="https://www.luogu.com.cn/problem/P1446">洛谷 P1446: Cards</a></li>
</ul>
</section>
<section id="probset-2" class="slide level2">
<h2>相关题目 #2</h2>
<ul>
<li><a href="https://www.luogu.com.cn/problem/P4128">洛谷 P4128: 有色图</a></li>
<li><a href="http://acm.hdu.edu.cn/showproblem.php?pid=5080">ICPC 2014 鞍山 K: Colorful Toy</a></li>
<li><a href="http://acm.hdu.edu.cn/showproblem.php?pid=6360">HDU 6360: Kaleidoscope</a></li>
<li><a href="https://nanti.jisuanke.com/t/42585">ICPC 2019 南昌 J: Summon</a></li>
<li><a href="https://nanti.jisuanke.com/t/42393">ICPC 2019 银川 M: Crazy Cake</a></li>
</ul>
<aside class="notes">
<p>本次讲解只讲了一些比较初步的应用，而给的题目里面很多更加灵活，不保证仅靠幻灯片里的内容就能解出这些题（狗头保命）……</p>
</aside>
</section>
<section id="reference" class="slide level2">
<h2>参考资料</h2>
<ul>
<li>近世代数引论/冯克勤,李尚志,章璞编著.-3版.-合肥：中国科学技术大学出版社,2009.12</li>
<li>近世代数初步/石生明.-2版.-北京：高等教育出版社,2006.3</li>
<li>Contemporary Abstract Algebra/Joseph A. Gallian.-8th Edition</li>
<li><a href="https://www.cnblogs.com/nosta/p/9444576.html">群论初探 - nosta - 博客园</a></li>
</ul>
</section></section>
    </div>
  </div>

  <script src="assets/revealjs/js/reveal.js"></script>

  <script>

      // Full list of configuration options available at:
      // https://github.com/hakimel/reveal.js#configuration
      Reveal.initialize({
        // Push each slide change to the browser history
        history: true,
        // The "normal" size of the presentation, aspect ratio will be preserved
        // when the presentation is scaled to fit different resolutions. Can be
        // specified using percentage units.
        width: 1366,
        height: 768,
        menu: {
            titleSelector: 'h1, h2',
            hideMissingTitles: true
        },
        // Optional reveal.js plugins
        dependencies: [
          { src: 'assets/revealjs/lib/js/classList.js', condition: function() { return !document.body.classList; } },
          { src: 'assets/revealjs/plugin/zoom-js/zoom.js', async: true },
          { src: 'assets/revealjs/plugin/menu/menu.js', async: true },
          { src: 'assets/revealjs/plugin/notes/notes.js', async: true }
        ]
      });
    </script>
    </body>
</html>